SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Semigroup with involution</title>

</head>

Semigroup with involution

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, particularly in <a href="Abstract_algebra" title="Abstract algebra">abstract algebra</a>, a semigroup with involution or a *-semigroup is a <a href="Semigroup" title="Semigroup">semigroup</a> equipped with an <a href="Involution_(mathematics)" title="Involution (mathematics)">involutive</a> <a href="Anti-automorphism" class="mw-redirect" title="Anti-automorphism">anti-automorphism</a>, which—roughly speaking—brings it closer to a <a href="Group_(mathematics)" title="Group (mathematics)">group</a> because this involution, considered as <a href="Unary_operator" class="mw-redirect" title="Unary operator">unary operator</a>, exhibits certain fundamental properties of the operation of taking the inverse in a group:

<ul><li><a href="Uniqueness_(mathematics)" class="mw-redirect" title="Uniqueness (mathematics)">Uniqueness</a></li>

<li>Double application "cancelling itself out".</li>

<li>The same interaction law with the binary operation as in the case of the group inverse.</li></ul>

It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

An example from <a href="Linear_algebra" title="Linear algebra">linear algebra</a> is a set of real-valued n-by-n square matrices with the matrix-transpose as the involution. The <a href="Map_(mathematics)" title="Map (mathematics)">map</a> which sends a matrix to its <a href="Transpose" title="Transpose">transpose</a> is an involution because the transpose is well defined for any matrix and obeys the law (AB)T = BTAT, which has the same form of interaction with multiplication as taking inverses has in the <a href="General_linear_group" title="General linear group">general linear group</a> (which is a subgroup of the full linear monoid). However, for an arbitrary matrix, AAT does not equal the identity element (namely the <a href="Diagonal_matrix" title="Diagonal matrix">diagonal matrix</a>). Another example, coming from <a href="Formal_language" title="Formal language">formal language</a> theory, is the <a href="Free_semigroup" class="mw-redirect" title="Free semigroup">free semigroup</a> generated by a <a href="Nonempty_set" class="mw-redirect" title="Nonempty set">nonempty set</a> (an <a href="Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a>), with string <a href="Concatenation" title="Concatenation">concatenation</a> as the binary operation, and the involution being the map which <a href="String_(computer_science)#Reversal" title="String (computer science)">reverses</a> the <a href="Linear_order" class="mw-redirect" title="Linear order">linear order</a> of the letters in a string. A third example, from basic <a href="Set_theory" title="Set theory">set theory</a>, is the set of all <a href="Binary_relation" title="Binary relation">binary relations</a> between a set and itself, with the involution being the <a href="Converse_relation" title="Converse relation">converse relation</a>, and the multiplication given by the usual <a href="Composition_of_relations" title="Composition of relations">composition of relations</a>.

Semigroups with involution appeared explicitly named in a 1953 paper of <a href="Viktor_Wagner" title="Viktor Wagner">Viktor Wagner</a> (in Russian) as result of his attempt to bridge the theory of semigroups with that of <a href="Semiheap" class="mw-redirect" title="Semiheap">semiheaps</a>.<a href="#cite_note-Hollings2014-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

Let S be a <a href="Semigroup" title="Semigroup">semigroup</a> with its binary operation written multiplicatively. An involution in S is a <a href="Unary_operation" title="Unary operation">unary operation</a> * on S (or, a transformation * : S → S, x ↦ x*) satisfying the following conditions:

The semigroup S with the involution * is called a semigroup with involution.

Semigroups that satisfy only the first of these axioms belong to the larger class of <a href="U-semigroup" class="mw-redirect" title="U-semigroup">U-semigroups</a>.

In some applications, the second of these axioms has been called <a href="Antidistributive" class="mw-redirect" title="Antidistributive">antidistributive</a>.<a href="#cite_note-BrinkKahl1997-2">[2]</a> Regarding the natural philosophy of this axiom, <a href="Harold_Scott_MacDonald_Coxeter" title="Harold Scott MacDonald Coxeter">H.S.M. Coxeter</a> remarked that it "becomes clear when we think of [x] and [y] as the operations of putting on our socks and shoes, respectively."<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<ol><li>If S is a <a href="Commutative" class="mw-redirect" title="Commutative">commutative</a> semigroup then the <a href="Identity_function" title="Identity function">identity map</a> of S is an involution.</li>

<li>If S is a <a href="Group_(mathematics)" title="Group (mathematics)">group</a> then the inversion map * : S → S defined by x* = x−1 is an involution. Furthermore, on an <a href="Abelian_group" title="Abelian group">abelian group</a> both this map and the one from the previous example are involutions satisfying the axioms of semigroup with involution.<a href="#cite_note-BergChristensen2012-4">[4]</a></li>

<li>If S is an <a href="Inverse_semigroup" title="Inverse semigroup">inverse semigroup</a> then the inversion map is an involution which leaves the <a href="Idempotent" class="mw-redirect" title="Idempotent">idempotents</a> <a href="Invariant_(mathematics)" title="Invariant (mathematics)">invariant</a>. As noted in the previous example, the inversion map is not necessarily the only map with this property in an inverse semigroup. There may well be other involutions that leave all idempotents invariant; for example the identity map on a commutative regular, hence inverse, semigroup, in particular, an abelian group. A <a href="Regular_semigroup" title="Regular semigroup">regular semigroup</a> is an <a href="Inverse_semigroup" title="Inverse semigroup">inverse semigroup</a> if and only if it admits an involution under which each idempotent is an invariant.<a href="#cite_note-5">[5]</a></li>

<li>Underlying every <a href="C*-algebra" title="C*-algebra">C*-algebra</a> is a *-semigroup. An important <a href="C*-algebra#Finite-dimensional_C*-algebras" title="C*-algebra">instance</a> is the algebra Mn(C) of n-by-n <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a> over <a href="Complex_number" title="Complex number">C</a>, with the <a href="Conjugate_transpose" title="Conjugate transpose">conjugate transpose</a> as involution.</li>

<li> If X is a set, the set of all <a href="Binary_relation" title="Binary relation">binary relations</a> on X is a *-semigroup with the * given by the <a href="Converse_relation" title="Converse relation">converse relation</a>, and the multiplication given by the usual <a href="Composition_of_relations" title="Composition of relations">composition of relations</a>. This is an example of a *-semigroup which is not a regular semigroup.</li>

<li> If X is a set, then the set of all finite sequences (or <a href="String_(computer_science)" title="String (computer science)">strings</a>) of members of X forms a <a href="Free_monoid" title="Free monoid">free monoid</a> under the operation of concatenation of sequences, with sequence reversal as an involution.</li>

<li> A <a href="Rectangular_band" class="mw-redirect" title="Rectangular band">rectangular band</a> on a Cartesian product of a set A with itself, i.e. with elements from A × A, with the semigroup product defined as (a, b)(c, d) = (a, d), with the involution being the order reversal of the elements of a pair (a, b)* = (b, a). This semigroup is also a <a href="Regular_semigroup" title="Regular semigroup">regular semigroup</a>, as all bands are.<a href="#cite_note-Nordahl_and_Scheiblich-6">[6]</a></li></ol>

<div class="mw-heading mw-heading2"><h2 id="Basic_concepts_and_properties">Basic concepts and properties</h2></div>

An element x of a semigroup with involution is sometimes called hermitian (by analogy with a <a href="Hermitian_matrix" title="Hermitian matrix">Hermitian matrix</a>) when it is left invariant by the involution, meaning x* = x. Elements of the form xx* or x*x are always hermitian, and so are all powers of a hermitian element. As noted in the examples section, a semigroup S is an <a href="Inverse_semigroup" title="Inverse semigroup">inverse semigroup</a> if and only if S is a <a href="Regular_semigroup" title="Regular semigroup">regular semigroup</a> and admits an involution such that every idempotent is hermitian.<a href="#cite_note-7">[7]</a>

Certain basic concepts may be defined on *-semigroups in a way that parallels the notions stemming from a <a href="Regular_semigroup" title="Regular semigroup">regular element in a semigroup</a>. A partial isometry is an element s such that ss*s = s; the set of partial isometries of a semigroup S is usually abbreviated PI(S).<a href="#cite_note-8">[8]</a> A projection is an idempotent element e that is also hermitian, meaning that ee = e and e* = e. Every projection is a partial isometry, and for every partial isometry s, s*s and ss* are projections. If e and f are projections, then e = ef if and only if e = fe.<a href="#cite_note-L117-9">[9]</a>

Partial isometries can be <a href="Partial_order" class="mw-redirect" title="Partial order">partially ordered</a> by s ≤ t defined as holding whenever s = ss*t and ss* = ss*tt*.<a href="#cite_note-L117-9">[9]</a> Equivalently, s ≤ t if and only if s = et and e = ett* for some projection e.<a href="#cite_note-L117-9">[9]</a> In a *-semigroup, PI(S) is an ordered groupoid with the <a href="Partial_groupoid" title="Partial groupoid">partial product</a> given by s⋅t = st if s*s = tt*.<a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading3"><h3 id="Examples_2">Examples</h3></div>

In terms of examples for these notions, in the *-semigroup of binary relations on a set, the partial isometries are the relations that are <a href="Difunctional" class="mw-redirect" title="Difunctional">difunctional</a>. The projections in this *-semigroup are the <a href="Partial_equivalence_relation" title="Partial equivalence relation">partial equivalence relations</a>.<a href="#cite_note-11">[11]</a><a href="#cite_note-12">[12]</a>

The <a href="Partial_isometry" title="Partial isometry">partial isometries</a> in a C*-algebra are exactly those defined in this section. In the case of Mn(C) more can be said. If E and F are projections, then E ≤ F if and only if <a href="Image_(mathematics)" title="Image (mathematics)">im</a>E ⊆ imF. For any two projection, if E ∩ F = V, then the unique projection J with image V and kernel the <a href="Orthogonal_complement" title="Orthogonal complement">orthogonal complement</a> of V is the meet of E and F. Since projections form a meet-<a href="Semilattice" title="Semilattice">semilattice</a>, the partial isometries on Mn(C) form an inverse semigroup with the product <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(A^{*}A\wedge BB^{*})B}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(A^{*}A\wedge BB^{*})B}</annotation>

</semantics>

</math><img src="./3f925b7d9679d749ec3de05601830368b41cb996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.022ex; height:2.843ex;" alt="{\displaystyle A(A^{*}A\wedge BB^{*})B}" loading="lazy">.<a href="#cite_note-13">[13]</a>

Another simple example of these notions appears in the next section.

<div class="mw-heading mw-heading2"><h2 id="Notions_of_regularity">Notions of regularity</h2></div>

There are two related, but not identical notions of regularity in *-semigroups. They were introduced nearly simultaneously by Nordahl & Scheiblich (1978) and respectively Drazin (1979).<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading3"><h3 id="Regular_*-semigroups_(Nordahl_&_Scheiblich)">Regular *-semigroups (Nordahl & Scheiblich)</h3></div>

As mentioned in the <a href="#Examples">previous examples</a>, <a href="Inverse_semigroup" title="Inverse semigroup">inverse semigroups</a> are a subclass of *-semigroups. It is also textbook knowledge that an inverse semigroup can be characterized as a regular semigroup in which any two idempotents commute. In 1963, <a href="Boris_M._Schein" title="Boris M. Schein">Boris M. Schein</a> showed that the following two axioms provide an analogous characterization of inverse semigroups as a <a href="Variety_(universal_algebra)" title="Variety (universal algebra)">subvariety</a> of *-semigroups:

The first of these looks like the definition of a regular element, but is actually in terms of the involution. Likewise, the second axiom appears to be describing the commutation of two idempotents. It is known however that regular semigroups do not form a variety because their class does not contain <a href="Free_object" title="Free object">free objects</a> (a result established by D. B. McAlister in 1968). This line of reasoning motivated Nordahl and Scheiblich to begin in 1977 the study of the (variety of) *-semigroups that satisfy only the first these two axioms; because of the similarity in form with the property defining regular semigroups, they named this variety regular *-semigroups.

It is a simple calculation to establish that a regular *-semigroup is also a regular semigroup because x* turns out to be an inverse of x. The rectangular band from <a href="#ex7">Example 7</a> is a regular *-semigroup that is not an inverse semigroup.<a href="#cite_note-Nordahl_and_Scheiblich-6">[6]</a> It is also easy to verify that in a regular *-semigroup the product of any two projections is an idempotent.<a href="#cite_note-15">[15]</a> In the aforementioned rectangular band example, the projections are elements of the form (x, x) and (like all elements of a band) are idempotent. However, two different projections in this band need not commute, nor is their product necessarily a projection since (a, a)(b, b) = (a, b).

Semigroups that satisfy only x** = x = xx*x (but not necessarily the antidistributivity of * over multiplication) have also been studied under the name of <a href="I-semigroup" class="mw-redirect" title="I-semigroup">I-semigroups</a>.

<div class="mw-heading mw-heading4"><h4 id="P-systems">P-systems</h4></div>

The problem of characterizing when a regular semigroup is a regular *-semigroup (in the sense of Nordahl & Scheiblich) can be addressed by defining a P-system. For the semigroup S, let E(S) denote the set of idempotents, and let V(a) denote the inverses of a. A P-system F(S) is then a subset of E(S) which satisfies the following axioms:

<ol><li>For any a in S, there exists a unique a° in V(a) such that aa° and a°a are in F(S)</li>

<li>For any a in S, and b in F(S), a°ba is in F(S), where ° is the well-defined operation from the previous axiom</li>

<li>For any a, b in F(S), ab is in E(S); note: not necessarily in F(S)</li></ol>

A regular semigroup S is a *-regular semigroup, if and only if it has a p-system F(S).<a href="#cite_note-16">[16]</a> In this case F(S) is the set of projections of S with respect to the operation ° defined by F(S). In an <a href="Inverse_semigroup" title="Inverse semigroup">inverse semigroup</a> the entire semilattice of idempotents is a P-system. Also, if a regular semigroup S has a P-system that is multiplicatively closed (i.e. subsemigroup), then S is an inverse semigroup. Thus, a P-system may be regarded as a generalization of the semilattice of idempotents of an inverse semigroup.

<div class="mw-heading mw-heading3"><h3 id="*-regular_semigroups_(Drazin)">*-regular semigroups (Drazin)</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

A semigroup S with an involution * is called a *-regular semigroup (in the sense of Drazin) if for every x in S, x* is H-equivalent to some inverse of x, where H is the <a href="Green's_relations" title="Green's relations">Green's relation</a> H. This defining property can be formulated in several equivalent ways. Another is to say that every <a href="Green's_relations#The_L.2C_R.2C_and_J_relations" title="Green's relations">L-class</a> contains a projection. An axiomatic definition is the condition that for every x in S there exists an element x′ such that x′xx′ = x′, xx′x = x, (xx′)* = xx′, (x′x)* = x′x. <a href="Michael_P._Drazin" title="Michael P. Drazin">Michael P. Drazin</a> first proved that given x, the element x′ satisfying these axioms is unique. It is called the Moore–Penrose inverse of x. This agrees with the classical definition of the <a href="Moore%E2%80%93Penrose_inverse" title="Moore–Penrose inverse">Moore–Penrose inverse</a> of a square matrix.

One motivation for studying these semigroups is that they allow generalizing the Moore–Penrose inverse's properties from ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation>

</semantics>

</math><img src="./786849c765da7a84dbc3cce43e96aad58a5868dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }" loading="lazy">⁠ and ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {C} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {C} }</annotation>

</semantics>

</math><img src="./f9add4085095b9b6d28d045fd9c92c2c09f549a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {C} }" loading="lazy">⁠ to more general sets.

In the <a href="Matrix_multiplication" title="Matrix multiplication">multiplicative</a> semigroup Mn(C) of square matrices of order n, the map which assigns a matrix A to its <a href="Hermitian_conjugate" class="mw-redirect" title="Hermitian conjugate">Hermitian conjugate</a> A* is an involution. The semigroup Mn(C) is a *-regular semigroup with this involution. The Moore–Penrose inverse of A in this *-regular semigroup is the classical Moore–Penrose inverse of A.

<div class="mw-heading mw-heading2"><h2 id="Free_semigroup_with_involution">Free semigroup with involution</h2></div>

As with all varieties, the <a href="Category_theory" title="Category theory">category</a> of semigroups with involution admits <a href="Free_object" title="Free object">free objects</a>. The construction of a free semigroup (or monoid) with involution is based on that of a <a href="Free_semigroup" class="mw-redirect" title="Free semigroup">free semigroup</a> (and respectively that of a free monoid). Moreover, the construction of a <a href="Free_group" title="Free group">free group</a> can easily be derived by refining the construction of a free monoid with involution.<a href="#cite_note-L51-17">[17]</a>

The <a href="Generator_(mathematics)" title="Generator (mathematics)">generators</a> of a free semigroup with involution are the elements of the union of two (<a href="Equinumerous" class="mw-redirect" title="Equinumerous">equinumerous</a>) <a href="Disjoint_sets" title="Disjoint sets">disjoint sets</a> in <a href="Bijection" title="Bijection">bijective correspondence</a>: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y=X\sqcup X^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y=X\sqcup X^{\dagger }}</annotation>

</semantics>

</math><img src="./87d757ba9e5418eebbf23791663e3803904adbc2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.393ex; height:2.676ex;" alt="{\displaystyle Y=X\sqcup X^{\dagger }}" loading="lazy">. (Here the notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sqcup }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sqcup }</annotation>

</semantics>

</math><img src="./1596aedf354da694149e44ce2bf53ede54eca8cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \sqcup }" loading="lazy"> emphasizes that the union is actually a <a href="Disjoint_union" title="Disjoint union">disjoint union</a>.) In the case were the two sets are finite, their union Y is sometimes called an <a href="Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a> with involution<a href="#cite_note-EhrenfeuchtHarju1999-18">[18]</a> or a symmetric alphabet.<a href="#cite_note-Sakarovitch-19">[19]</a> Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta :X\rightarrow X^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta :X\rightarrow X^{\dagger }}</annotation>

</semantics>

</math><img src="./f0858a78934faeab6de9aa2c8c3a78c38ae0f3d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.581ex; height:2.676ex;" alt="{\displaystyle \theta :X\rightarrow X^{\dagger }}" loading="lazy"> be a bijection; <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> is naturally <a href="Function_(mathematics)#Restrictions_and_extensions" title="Function (mathematics)">extended</a> to a bijection <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {}\dagger :Y\to Y}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {}\dagger :Y\to Y}</annotation>

</semantics>

</math><img src="./5fe07544522e8050d97214386f380877f24019cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.13ex; height:2.676ex;" alt="{\displaystyle {}\dagger :Y\to Y}" loading="lazy"> essentially by taking the disjoint union of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> (as a set) with its <a href="Inverse_function" title="Inverse function">inverse</a>, or in <a href="Piecewise" class="mw-redirect" title="Piecewise">piecewise</a> notation:<a href="#cite_note-Lipscomb1996-20">[20]</a>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{\dagger }={\begin{cases}\theta (y)&{\text{if }}y\in X\\\theta ^{-1}(y)&{\text{if }}y\in X^{\dagger }\end{cases}}}</annotation>

</semantics>

</math>

Now construct <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}\,}</annotation>

</semantics>

</math><img src="./3446000dcca1c9afd36e7a449176c3bdab8aff47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.798ex; height:2.343ex;" alt="{\displaystyle Y^{+}\,}" loading="lazy"> as the <a href="Free_semigroup" class="mw-redirect" title="Free semigroup">free semigroup</a> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y\,}</annotation>

</semantics>

</math><img src="./b9e3deb85bd2bfe306da34e635f7bfb2926daf8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:2.16ex; height:2.009ex;" alt="{\displaystyle Y\,}" loading="lazy"> in the usual way with the binary (semigroup) operation on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}\,}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=w_{1}w_{2}\cdots w_{k}\in Y^{+}}</annotation>

</semantics>

</math> for some letters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}\in Y.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}\in Y.}</annotation>

</semantics>

</math><img src="./0284320350a0b82466fd75e30903db812f2acebd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.725ex; height:2.509ex;" alt="{\displaystyle w_{i}\in Y.}" loading="lazy">

The bijection <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \dagger }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \dagger }</annotation>

</semantics>

</math><img src="./2fbce70d5be6fec538cd30d8bc7b7bb2d3ed2d3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.032ex; height:2.676ex;" alt="{\displaystyle \dagger }" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> is then extended as a bijection <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {}^{\dagger }:Y^{+}\rightarrow Y^{+}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {}^{\dagger }:Y^{+}\rightarrow Y^{+}}</annotation>

</semantics>

</math><img src="./46d70cd5d2587c38de0db6f05a63f9ea0adb77a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.336ex; height:2.676ex;" alt="{\displaystyle {}^{\dagger }:Y^{+}\rightarrow Y^{+}}" loading="lazy"> defined as the string reversal of the elements of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}\,}</annotation>

</semantics>

</math><img src="./3446000dcca1c9afd36e7a449176c3bdab8aff47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.798ex; height:2.343ex;" alt="{\displaystyle Y^{+}\,}" loading="lazy"> that consist of more than one letter:<a href="#cite_note-EhrenfeuchtHarju1999-18">[18]</a><a href="#cite_note-Lipscomb1996-20">[20]</a>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w^{\dagger }=w_{k}^{\dagger }w_{k-1}^{\dagger }\cdots w_{2}^{\dagger }w_{1}^{\dagger }.}</annotation>

</semantics>

</math>

This map is an <a href="#Formal_definition">involution</a> on the semigroup <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}\,}</annotation>

</semantics>

</math><img src="./3446000dcca1c9afd36e7a449176c3bdab8aff47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.798ex; height:2.343ex;" alt="{\displaystyle Y^{+}\,}" loading="lazy">. Thus, the semigroup <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X\sqcup X^{\dagger })^{+}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X\sqcup X^{\dagger })^{+}}</annotation>

</semantics>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {}^{\dagger }\,}</annotation>

</semantics>

</math><img src="./337a7ec66fd764eaa9bfec55ee5eed8bb98171c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.349ex; height:2.509ex;" alt="{\displaystyle {}^{\dagger }\,}" loading="lazy"> is a semigroup with involution, called a free semigroup with involution on X.<a href="#cite_note-L172-21">[21]</a> (The irrelevance of the concrete identity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X^{\dagger }}</annotation>

</semantics>

</math><img src="./5b31335fa0abde1543f245fe140e1516948435d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.959ex; height:2.676ex;" alt="{\displaystyle X^{\dagger }}" loading="lazy"> and of the bijection <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> in this choice of terminology is explained below in terms of the universal property of the construction.) Note that unlike in <a href="#ex6">Example 6</a>, the involution of every letter is a distinct element in an alphabet with involution, and consequently the same observation extends to a free semigroup with involution.

If in the above construction instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}\,}</annotation>

</semantics>

</math><img src="./3446000dcca1c9afd36e7a449176c3bdab8aff47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.798ex; height:2.343ex;" alt="{\displaystyle Y^{+}\,}" loading="lazy"> we use the <a href="Free_monoid" title="Free monoid">free monoid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}=Y^{+}\cup \{\varepsilon \}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}=Y^{+}\cup \{\varepsilon \}}</annotation>

</semantics>

</math><img src="./9daa46b6ea2ef422e58e061afdde723aeb2ef016.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.455ex; height:3.009ex;" alt="{\displaystyle Y^{*}=Y^{+}\cup \{\varepsilon \}}" loading="lazy">, which is just the free semigroup extended with the <a href="Empty_word" class="mw-redirect" title="Empty word">empty word</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon \,}</annotation>

</semantics>

</math><img src="./137e3f3e97dfca591286d3815815dd6470bdf77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.471ex; height:1.676ex;" alt="{\displaystyle \varepsilon \,}" loading="lazy"> (which is the <a href="Identity_element" title="Identity element">identity element</a> of the <a href="Monoid" title="Monoid">monoid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}\,}</annotation>

</semantics>

</math><img src="./f0e4012cf40486f755a641b4388c976daf0957e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.342ex; height:2.176ex;" alt="{\displaystyle Y^{*}\,}" loading="lazy">), and suitably extend the involution with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon ^{\dagger }=\varepsilon }">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon ^{\dagger }=\varepsilon }</annotation>

</semantics>

</math><img src="./39172ded7add493ec9341171828ce89e31521593.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.228ex; height:2.676ex;" alt="{\displaystyle \varepsilon ^{\dagger }=\varepsilon }" loading="lazy">,

we obtain a free monoid with involution.<a href="#cite_note-Lipscomb1996-20">[20]</a>

The construction above is actually the only way to extend a given map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \,}</annotation>

</semantics>

</math><img src="./228647b7d4a18b6c8c0c390b439a61da8fafec76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.478ex; height:2.176ex;" alt="{\displaystyle \theta \,}" loading="lazy"> from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\,}</annotation>

</semantics>

</math><img src="./7028e89b7722d12ec0ea8780f26a9912456b63f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.367ex; height:2.176ex;" alt="{\displaystyle X\,}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X^{\dagger }\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X^{\dagger }\,}</annotation>

</semantics>

</math><img src="./4994c6e025b4414fdccb9cd423e8d7b3c29c35e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.346ex; height:2.676ex;" alt="{\displaystyle X^{\dagger }\,}" loading="lazy">, to an involution on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{+}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{+}}</annotation>

</semantics>

</math><img src="./128e1b963abf30df4d90ad0ce05c6e5f937e2190.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.411ex; height:2.343ex;" alt="{\displaystyle Y^{+}}" loading="lazy"> (and likewise on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}\,}</annotation>

</semantics>

</math><img src="./f0e4012cf40486f755a641b4388c976daf0957e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.342ex; height:2.176ex;" alt="{\displaystyle Y^{*}\,}" loading="lazy">). The qualifier "free" for these constructions is justified in the usual sense that they are <a href="Universal_algebra" title="Universal algebra">universal constructions</a>. In the case of the free semigroup with involution, given an arbitrary semigroup with involution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy"> and a map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi :X\rightarrow S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi :X\rightarrow S}</annotation>

</semantics>

</math><img src="./9560fb243fcc374d0a58cf98b9db976b639b1765.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.709ex; height:2.176ex;" alt="{\displaystyle \Phi :X\rightarrow S}" loading="lazy">, then a <a href="Semigroup_homomorphism" class="mw-redirect" title="Semigroup homomorphism">semigroup homomorphism</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overline {\Phi }}:(X\sqcup X^{\dagger })^{+}\rightarrow S}">

<mover>

</mover>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overline {\Phi }}:(X\sqcup X^{\dagger })^{+}\rightarrow S}</annotation>

</semantics>

</math><img src="./5e2541d8f066010d6a34042279edcd45a439f02c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.685ex; height:3.509ex;" alt="{\displaystyle {\overline {\Phi }}:(X\sqcup X^{\dagger })^{+}\rightarrow S}" loading="lazy"> exists such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi =\iota \circ {\overline {\Phi }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi =\iota \circ {\overline {\Phi }}}</annotation>

</semantics>

</math><img src="./b473f291a64716459f998c4b20f3986172fc914c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.588ex; height:3.009ex;" alt="{\displaystyle \Phi =\iota \circ {\overline {\Phi }}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \iota :X\rightarrow (X\sqcup X^{\dagger })^{+}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \iota :X\rightarrow (X\sqcup X^{\dagger })^{+}}</annotation>

</semantics>

</math><img src="./adc2132c46370c5765bf22d0d9580da3b1a281b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.196ex; height:3.176ex;" alt="{\displaystyle \iota :X\rightarrow (X\sqcup X^{\dagger })^{+}}" loading="lazy"> is the <a href="Inclusion_map" title="Inclusion map">inclusion map</a> and <a href="Composition_of_functions" class="mw-redirect" title="Composition of functions">composition of functions</a> is taken in <a href="Function_composition#Alternative_notations" title="Function composition">diagram order</a>.<a href="#cite_note-L172-21">[21]</a> The construction of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X\sqcup X^{\dagger })^{+}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X\sqcup X^{\dagger })^{+}}</annotation>

</semantics>

</math><img src="./58d313246098c98a4bbe086a716c4675b1dc31ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.842ex; height:3.176ex;" alt="{\displaystyle (X\sqcup X^{\dagger })^{+}}" loading="lazy"> as a semigroup with involution is unique up to <a href="Isomorphism" title="Isomorphism">isomorphism</a>. An analogous argument holds for the free monoid with involution in terms of <a href="Monoid_homomorphism" class="mw-redirect" title="Monoid homomorphism">monoid homomorphisms</a> and the uniqueness up to isomorphism of the construction of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X\sqcup X^{\dagger })^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X\sqcup X^{\dagger })^{*}}</annotation>

</semantics>

</math><img src="./0b477f67df75ad45531acd40cf3352211d09a099.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.385ex; height:3.176ex;" alt="{\displaystyle (X\sqcup X^{\dagger })^{*}}" loading="lazy"> as a monoid with involution.

The construction of a <a href="Free_group" title="Free group">free group</a> is not very far off from that of a free monoid with involution. The additional ingredient needed is to define a notion of <a href="Reduced_word" class="mw-redirect" title="Reduced word">reduced word</a> and a <a href="Rewriting" title="Rewriting">rewriting</a> rule for producing such words simply by deleting any adjacent pairs of letter of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xx^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xx^{\dagger }}</annotation>

</semantics>

</math><img src="./58315544fc52729718891d012bf49f0b265e53c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.622ex; height:2.676ex;" alt="{\displaystyle xx^{\dagger }}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{\dagger }x}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{\dagger }x}</annotation>

</semantics>

</math><img src="./0fc188171411ee9bd239db3eb70e7b3e61bb94b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.622ex; height:2.676ex;" alt="{\displaystyle x^{\dagger }x}" loading="lazy">. It can be shown than the order of rewriting (deleting) such pairs does not matter, i.e. any order of deletions produces the same result.<a href="#cite_note-L51-17">[17]</a> (Otherwise put, these rules define a <a href="Confluence_(abstract_rewriting)" title="Confluence (abstract rewriting)">confluent</a> rewriting system.) Equivalently, a free group is constructed from a free monoid with involution by taking the <a href="Quotient_(universal_algebra)" title="Quotient (universal algebra)">quotient</a> of the latter by the <a href="Congruence_relation" title="Congruence relation">congruence</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{(yy^{\dagger },\varepsilon ):y\in Y\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{(yy^{\dagger },\varepsilon ):y\in Y\}}</annotation>

</semantics>

</math><img src="./c9ca6a816a3011d50d657771f4a7023002a657fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.236ex; height:3.176ex;" alt="{\displaystyle \{(yy^{\dagger },\varepsilon ):y\in Y\}}" loading="lazy">, which is sometimes called the Dyck congruence—in a certain sense it generalizes <a href="Dyck_language" title="Dyck language">Dyck language</a> to multiple kinds of "parentheses" However simplification in the Dyck congruence takes place regardless of order. For example, if ")" is the inverse of "(", then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ()=)(=\varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ()=)(=\varepsilon }</annotation>

</semantics>

</math><img src="./fa750ca9ae3504c4e3ca9c75ef61ab2766b1b168.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.609ex; height:2.843ex;" alt="{\displaystyle ()=)(=\varepsilon }" loading="lazy">; the one-sided congruence that appears in the Dyck language proper <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{(xx^{\dagger },\varepsilon ):x\in X\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{(xx^{\dagger },\varepsilon ):x\in X\}}</annotation>

</semantics>

</math><img src="./27421965ec851b332b06cc71c16bd57996ea943b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.961ex; height:3.176ex;" alt="{\displaystyle \{(xx^{\dagger },\varepsilon ):x\in X\}}" loading="lazy">, which instantiates only to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ()=\varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ()=\varepsilon }</annotation>

</semantics>

</math><img src="./64e3e67dac691ac241ded25b93c11ca718edaf3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.991ex; height:2.843ex;" alt="{\displaystyle ()=\varepsilon }" loading="lazy"> is (perhaps confusingly) called the Shamir congruence. The quotient of a free monoid with involution by the Shamir congruence is not a group, but a monoid ; nevertheless it has been called the free half group by its first discoverer—<a href="Eli_Shamir" title="Eli Shamir">Eli Shamir</a>—although more recently it has been called the involutive monoid generated by X.<a href="#cite_note-Sakarovitch-19">[19]</a><a href="#cite_note-DrosteKuich2009-22">[22]</a> (This latter choice of terminology conflicts however with the use of "involutive" to denote any semigroup with involution—a practice also encountered in the literature.<a href="#cite_note-Neeb2000-23">[23]</a><a href="#cite_note-BeltramettiCassinelli2010-24">[24]</a>)

<div class="mw-heading mw-heading2"><h2 id="Baer_*-semigroups">Baer *-semigroups</h2></div>

A Baer *-semigroup is a *-semigroup with (two-sided) zero in which the right annihilator of every element coincides with the <a href="Semigroup_ideal" class="mw-redirect" title="Semigroup ideal">right ideal</a> of some projection; this property is expressed formally as: for all x ∈ S there exists a projection e such that

The projection e is in fact uniquely determined by x.<a href="#cite_note-BeltramettiCassinelli2010-24">[24]</a>

More recently, Baer *-semigroups have been also called Foulis semigroups, after <a href="David_James_Foulis" class="mw-redirect" title="David James Foulis">David James Foulis</a> who studied them in depth.<a href="#cite_note-Blyth2006-25">[25]</a><a href="#cite_note-26">[26]</a>

<div class="mw-heading mw-heading3"><h3 id="Examples_and_applications">Examples and applications</h3></div>

The set of all binary relations on a set (from <a href="#ex5">example 5</a>) is a Baer *-semigroup.<a href="#cite_note-Foulis63-27">[27]</a>

Baer *-semigroups are also encountered in <a href="Quantum_mechanics" title="Quantum mechanics">quantum mechanics</a>,<a href="#cite_note-BeltramettiCassinelli2010-24">[24]</a> in particular as the multiplicative semigroups of <a href="Baer_*-ring" class="mw-redirect" title="Baer *-ring">Baer *-rings</a>.

If H is a <a href="Hilbert_space" title="Hilbert space">Hilbert space</a>, then the multiplicative semigroup of all <a href="Bounded_operator" title="Bounded operator">bounded operators</a> on H is a Baer *-semigroup. The involution in this case maps an operator to its <a href="Adjoint_operator" class="mw-redirect" title="Adjoint operator">adjoint</a>.<a href="#cite_note-Foulis63-27">[27]</a>

Baer *-semigroup allow the coordinatization of <a href="Orthomodular_lattice" class="mw-redirect" title="Orthomodular lattice">orthomodular lattices</a>.<a href="#cite_note-Blyth2006-25">[25]</a>

<ul><li><a href="Dagger_category" title="Dagger category">Dagger category</a> (aka category with involution) — generalizes *-monoids</li>

<li><a href="*-algebra" title="*-algebra">*-algebra</a></li>

<li><a href="Special_classes_of_semigroups" title="Special classes of semigroups">Special classes of semigroups</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Hollings2014-1"><a href="#cite_ref-Hollings2014_1-0">^</a> <a href="#CITEREFHollings2014">Hollings (2014</a>:265)

</li>

<li id="cite_note-BrinkKahl1997-2"><a href="#cite_ref-BrinkKahl1997_2-0">^</a> <a href="#CITEREFBrinkKahlSchmidt1997">Brink, Kahl & Schmidt (1997</a>:4)

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFCoxeter1961">Coxeter (1961</a>:33)

</li>

<li id="cite_note-BergChristensen2012-4"><a href="#cite_ref-BergChristensen2012_4-0">^</a> <a href="#CITEREFvan_den_BergChristensenRessel2012">van den Berg, Christensen & Ressel (2012</a>:87–88)

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Munn, Lemma 1

</li>

<li id="cite_note-Nordahl_and_Scheiblich-6">^ <a href="#cite_ref-Nordahl_and_Scheiblich_6-0">a</a> <a href="#cite_ref-Nordahl_and_Scheiblich_6-1">b</a> Nordahl and Scheiblich

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFEasdownMunn1993">Easdown & Munn (1993)</a>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:116)

</li>

<li id="cite_note-L117-9">^ <a href="#cite_ref-L117_9-0">a</a> <a href="#cite_ref-L117_9-1">b</a> <a href="#cite_ref-L117_9-2">c</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:117)

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:118)

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:122)

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:35)

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:120)

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> Crvenkovic and Dolinka

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> Nordahl and Scheiblich, Theorem 2.5

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <a href="#CITEREFYamada1982">Yamada (1982)</a>

</li>

<li id="cite_note-L51-17">^ <a href="#cite_ref-L51_17-0">a</a> <a href="#cite_ref-L51_17-1">b</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:51)

</li>

<li id="cite_note-EhrenfeuchtHarju1999-18">^ <a href="#cite_ref-EhrenfeuchtHarju1999_18-0">a</a> <a href="#cite_ref-EhrenfeuchtHarju1999_18-1">b</a> <a href="#CITEREFEhrenfeuchtHarjuRozenberg1999">Ehrenfeucht, Harju & Rozenberg (1999</a>:13–14)

</li>

<li id="cite_note-Sakarovitch-19">^ <a href="#cite_ref-Sakarovitch_19-0">a</a> <a href="#cite_ref-Sakarovitch_19-1">b</a> <a href="#CITEREFSakarovitch2009">Sakarovitch (2009</a>:305–306)

</li>

<li id="cite_note-Lipscomb1996-20">^ <a href="#cite_ref-Lipscomb1996_20-0">a</a> <a href="#cite_ref-Lipscomb1996_20-1">b</a> <a href="#cite_ref-Lipscomb1996_20-2">c</a> <a href="#CITEREFLipscomb1996">Lipscomb (1996</a>:86)

</li>

<li id="cite_note-L172-21">^ <a href="#cite_ref-L172_21-0">a</a> <a href="#cite_ref-L172_21-1">b</a> <a href="#CITEREFLawson1998">Lawson (1998</a>:172)

</li>

<li id="cite_note-DrosteKuich2009-22"><a href="#cite_ref-DrosteKuich2009_22-0">^</a> <a href="#CITEREFPetreSalomaa2009">Petre & Salomaa (2009</a>:271)

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKarl-Hermann_Neeb2000" class="citation book cs1">Karl-Hermann Neeb (2000). Holomorphy and Convexity in Lie Theory. Walter de Gruyter. p. 21. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-11-015669-0</bdi>.</cite>

</li>

<li id="cite_note-BeltramettiCassinelli2010-24">^ <a href="#cite_ref-BeltramettiCassinelli2010_24-0">a</a> <a href="#cite_ref-BeltramettiCassinelli2010_24-1">b</a> <a href="#cite_ref-BeltramettiCassinelli2010_24-2">c</a> <a href="#cite_ref-BeltramettiCassinelli2010_24-3">d</a> <cite id="CITEREFEnrico_G._BeltramettiGianni_Cassinelli2010" class="citation book cs1">Enrico G. Beltrametti; Gianni Cassinelli (2010) [1981]. The Logic of Quantum Mechanics. Cambridge University Press. p. 178. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-16849-6</bdi>.</cite>

</li>

<li id="cite_note-Blyth2006-25">^ <a href="#cite_ref-Blyth2006_25-0">a</a> <a href="#cite_ref-Blyth2006_25-1">b</a> <cite id="CITEREFT.S._Blyth2006" class="citation book cs1">T.S. Blyth (2006). Lattices and Ordered Algebraic Structures. Springer Science & Business Media. pp. 101–102. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-84628-127-3</bdi>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> Harding, John. "Daggers, Kernels, Baer *-Semigroups, and Orthomodularity". Journal of Philosophical Logic. 6 April 2013. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10992-013-9275-5">10.1007/s10992-013-9275-5</a>

</li>

<li id="cite_note-Foulis63-27">^ <a href="#cite_ref-Foulis63_27-0">a</a> <a href="#cite_ref-Foulis63_27-1">b</a> Foulis, D. J. Relative inverses in Baer *-semigroups. Michigan Math. J. 10 (1963), no. 1, 65–84. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1307%2Fmmj%2F1028998825">10.1307/mmj/1028998825</a>.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>D J Foulis (1958). Involution Semigroups, PhD Thesis, Tulane University, New Orleans, LA. <a rel="nofollow" class="external text" href="http://www.math.umass.edu/~foulis/publ.txt">Publications of D.J. Foulis</a> (Accessed on 5 May 2009)</li>

<li><cite id="CITEREFCoxeter1961" class="citation book cs1"><a href="Donald_Coxeter" class="mw-redirect" title="Donald Coxeter">Coxeter, H.S.M.</a> (1961). Introduction to Geometry.</cite></li>

<li>W.D. Munn, Special Involutions, in A.H. Clifford, K.H. Hofmann, M.W. Mislove, Semigroup theory and its applications: proceedings of the 1994 conference commemorating the work of Alfred H. Clifford, Cambridge University Press, 1996, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0521576695</bdi>.</li>

<li>Drazin, M.P., Regular semigroups with involution, Proc. Symp. on Regular Semigroups (DeKalb, 1979), 29–46</li>

<li>Nordahl, T.E., and H.E. Scheiblich, Regular * Semigroups, <a href="Semigroup_Forum" title="Semigroup Forum">Semigroup Forum</a>, 16(1978), 369–377.</li>

<li><cite id="CITEREFYamada1982" class="citation cs2">Yamada, Miyuki (December 1982), "P-systems in regular semigroups", <a href="Semigroup_Forum" title="Semigroup Forum">Semigroup Forum</a>, 24 (1): 173–187</cite></li>

<li><cite id="CITEREFEasdownMunn1993" class="citation cs2">Easdown, David; Munn, Walter Douglas (1993), "On semigroups with involution", Bulletin of the Australian Mathematical Society, 48 (1): 93–100, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0004972700015495">10.1017/S0004972700015495</a></cite></li>

<li><cite id="CITEREFLipscomb1996" class="citation book cs1">Lipscomb, Stephen (1996). Symmetric Inverse Semigroups. American Mathematical Soc. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-0627-2</bdi>.</cite></li>

<li><cite id="CITEREFBrinkKahlSchmidt1997" class="citation book cs1">Brink, Chris; Kahl, Wolfram; Schmidt, Gunther (1997). Relational Methods in Computer Science. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-211-82971-4</bdi>.</cite></li>

<li><cite id="CITEREFLawson1998" class="citation book cs1">Lawson, Mark (1998). Inverse semigroups: the theory of partial symmetries. <a href="World_Scientific" title="World Scientific">World Scientific</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>981-02-3316-7</bdi>.</cite></li>

<li><cite id="CITEREFEhrenfeuchtHarjuRozenberg1999" class="citation book cs1">Ehrenfeucht, Andrzej; Harju, T.; Rozenberg, Grzegorz (1999). The Theory of 2-structures: A Framework for Decomposition and Transformation of Graphs. World Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-981-02-4042-4</bdi>.</cite></li>

<li>S. Crvenkovic and Igor Dolinka, "<a rel="nofollow" class="external text" href="http://people.dmi.uns.ac.rs/~dockie/papers/031.pdf">Varieties of involution semigroups and involution semirings: a survey</a>", Bulletin of the Society of Mathematicians of Banja Luka Vol. 9 (2002), 7–47.</li>

<li><cite id="CITEREFSakarovitch2009" class="citation book cs1">Sakarovitch, Jacques (2009). Elements of Automata Theory. Cambridge University Press.</cite></li>

<li><cite id="CITEREFPetreSalomaa2009" class="citation book cs1">Petre, Ion; <a href="Arto_Salomaa" title="Arto Salomaa">Salomaa, Arto</a> (2009). "Algebraic Systems and Pushdown Automata". In Manfred Droste; Werner Kuich; Heiko Vogler (eds.). Handbook of Weighted Automata. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-01492-5</bdi>.</cite></li>

<li><cite id="CITEREFvan_den_BergChristensenRessel2012" class="citation book cs1">van den Berg, C.; Christensen, J. P. R.; Ressel, P. (2012). Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Springer Science & Business Media. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4612-1128-0</bdi>.</cite></li>

<li><cite id="CITEREFHollings2014" class="citation book cs1">Hollings, Christopher (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. <a href="American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4704-1493-1</bdi>.</cite></li>

<li>This article incorporates material from Free semigroup with involution on <a href="PlanetMath" title="PlanetMath">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.</li></ul>

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-27" href="https://en.wikipedia.org/wiki/?title=Semigroup_with_involution&oldid=1287576951">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>